给定一个正整数 ,求它的一个倍数 使得 只含有数字 和 。
我们可以 开始进行 ,设当前搜索到的数为 ,则下一次从 和 进行搜索,搜到 的倍数直接退出。
题目说 不超过 位,为了避免写高精度,我们可以把当前搜索到的数模 的余数传入 ,而把搜索到的数作为字符串,每次在末尾添上 ,同时记录数字的位数,位数到达 停止搜索。
为了加快效率,我们可以加一个剪枝,搜索到一个可行解后停止搜索。
实测效率还是比较快的,代码也很简短,应该很容易理解。
Code
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int n, flag;
void dfs(string s, int cnt, int mod) {
if (cnt >= 100 || flag) return;
if (mod == 0) {
flag = 1;
cout << s << endl;
return;
}
dfs(s + '0', cnt + 1, mod * 10 % n);
dfs(s + '1', cnt + 1, (mod * 10 + 1) % n);
}
int main() {
while (~scanf("%d", &n) && n) {
flag = 0;
dfs("1", 1, 1);
}
return 0;
}